Characterisation of Non-Unique Base b-expansions

There are many proofs in which working with the expansions of real numbers in a given base feels like it would give the nicest argument, however the non-uniqueness of such expansions often leads to problems.

It seems though that this non-uniqueness is localised to a particular type of problem. In base 10, considering non-unique expansions seem to all be (loosely speaking) of the same form:

0.99900…=1.00000…0.05999…=0.06000…0.00199…=0.00200…

Indeed this is the case, and the following theorem describes this rigorously to classify non-unique expansions completely.

We isolate the problem here such that proofs like the uncountability of the real numbers can handle these issues.

Theorem

Let x,y∈[0,1), and let xn and yn be the corresponding digits of each number in their base b expansion (after the decimal point, starting index at 1). That is, xn,yn∈{0,…,b−1} for all n≥1.

If the base b expansions of x and y given above are distinct, then we have that x=y if and only if (up to reordering) there exists an N such that

  1. n<N⟹xn=yn
  2. n=N⟹xn=yn−1
  3. n>N⟹xn=b−1∧yn=0
Proof

Assume that x=y∈[0,1), and write x=∑k=1∞xkb−k and y=∑k=1∞xkb−k, the base b expansions of each x and y, which are distinct.

Let N be the least positive integer such that xN≠yN. Now consider that

0=y−x=∑k=1∞ykb−k−∑k=1∞xkb−k=∑k=1∞(yk−xk)b−k=∑k=N∞(yk−xk)b−k=(yN−xN)b−N+∑k=N+1∞(yk−xk)b−k≤(yN−xN)b−N+(b−1)∑k=N+1∞b−k=(yN−xN)b−N+(b−1)1b−(N+1)1−1b=(yN−xN)b−N+1bN

hence

0≤(yN−xN)b−N+1bN=(yN−xN+1)b−1

and therefore

yN−xN+1≥0⟹yN−xN≥−1⟹xN−yN≤1.

The symmetrical argument above similarly shows that xN−yN≤1 and hence we have that |xN−yN|≤1. Since we assumed that xN≠yN⟹xN−yN≠0, we have that |xN−yN|=1. As such, we assume without loss of generality that xN=yN−1 (the other argument follows identically).

Returning to our calculation of the difference, we now have that

0=x−y=(xN−yN)b−N+∑k=N+1∞(xk−yk)b−k=−b−N+∑k=N+1∞(xk−yk)b−kb−N=∑k=N+1∞(xk−yk)b−k.

We know that the right hand side is upper bounded by b−N and since this is the left hand side, equality happens when the right hand side achieves this upper bound. If any xk−yk is not b−1 then the sum can be at most b−N−((b−1)−(xk−yk))b−k. For example in base 10, if one digit is 8, in the kth place, then the sum is bounded by 10−N−8⋅10−k. As such we have that xk−yk=b−1 for all k>N. Since xk and yk are in {0,…,b−1}, the only way this is possible is by maximising xk and minimising yk, that is xk=b−1 and yk=0 for all k>N.

This proves the forward implication.

Reverse implication is relatively straightforward. That is, if we assume that

  1. n<N⟹xn=yn
  2. n=N⟹xn=yn−1
  3. n>N⟹xn=b−1∧yn=0

as above, then we have that

x−y=∑k=1∞xkb−k−∑k=1∞ykb−k=∑k=1∞(xk−yk)b−k=∑k=N∞(xk−yk)b−k=−b−N+∑k=N+1∞(b−1)b−k=−b−N+bN=0.